if __name__ == "__main__":
    try:
        a = int(input("请输入一个整数:"))
        m = int(input("请输入模:"))
    except ValueError:
        print("输入无效，请输入整数。")
    else:
        if a < m:
            a, m = m, a
            x1, x2,x3= 1, 0, a
            y1, y2,y3= 0, 1, m
            while y3 != 0:
                Q = x3//y3
                t1, t2, t3 = x1 - Q*y1, x2 - Q*y2, x3 - Q*y3
                x1, x2, x3 = y1, y2, y3
                y1, y2, y3 = t1, t2, t3
            print(x2)
        else:
            x1, x2, x3 = 1, 0, a
            y1, y2, y3 = 0, 1, m
            while y3 != 0:
                Q = x3 // y3
                t1, t2, t3 = x1 - Q*y1, x2 - Q*y2, x3 - Q*y3
                x1, x2, x3 = y1, y2, y3
                y1, y2, y3 = t1, t2, t3
            print(x1)
